The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
The transmission of data packets across a computing network typically involves a series of “hops” at a number of intermediary networking devices, often various types of routers, before each data packet reaches its destination. When each of these intermediary networking devices receives a data packet, the devices may be configured to perform any of a variety of actions with the data packet based on address information specified by the network packet, such as a source address, destination address, or path information. For example, an Internet Protocol (IP) data packet may include a destination IP address field within the header of the IP data packet, based upon which a network router may determine one or more other networking devices, among a number of possible other networking devices to forward the IP data packet to.
The information used by such networking devices to determine how to handle data packets based on specified address information is generally referred to herein as routing information, and is commonly represented in a table format. A table may associate an address with policy or rule information that dictates the actions that the router is to perform with any data packet that is associated with the address. Such a table may also be referred to as a policy table. A router may be configured to consult different types of tables for different purposes. For instance, a router may include one policy table describing policies to apply based on source address information at one network layer, another policy table describing policies to apply based on destination address information at another network layer, and yet other policy tables that serves yet other purposes.
Rather than including a separate record, or entry, for each possible address, a table may be configured such that each entry of the table specifies policy information for a different group of addresses. For example, each entry in an IP-based forwarding table may specify a group of IP addresses and a “next hop” device identifier, indicating that any data packet specifying a destination address that is a part of the specified group of IP addresses is to be forwarded to the specified next hop device. One common manner of specifying a group of addresses is by a common prefix that each of the addresses shares. Generally, a prefix is a first portion of a network address. A prefix may be of any length, and thus any given address may have, or “match,” multiple prefixes. For example, the prefixes 192, 192.168, and 192.168.1 would all be valid prefixes for the address 192.168.1.1. Prefixes may be described with the routing information of a router in a variety of manners, some of which are described herein.
Many types of routers distribute a significant number of data packets on a nearly continuous basis. Thus, the speed at which networking devices are able to process received network packets can be of great importance. For these reasons and others, routing information and other similar data may be stored in a networking device using specialized high-speed memory components, such as content addressable memory (CAM). However, the use of such high-speed memory in networking devices is relatively expensive, both in terms of cost and power consumption. Thus, more efficient techniques for storing and searching routing information are desirable, particularly as the number of routing entries stored by a networking device grows large.